/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-pivot-index
   @Language: C++
   @Datetime: 19-05-13 15:03
   */

class Solution {
public:
	/**
	 * @param nums: an array
	 * @return: the "pivot" index of this array
	 */
	int pivotIndex(vector<int> &nums) {
		// Write your code here
		vector<int> sums(nums.size()+1,0);
		for(int i=0; i<nums.size(); ++i)
			sums[i+1]=sums[i]+nums[i];
		for(int i=0; i<nums.size(); ++i)
			if(sums[i]==sums[nums.size()]-sums[i]-nums[i])
				return i;
		return -1;
	}
};
